#include "Solvers.hpp"
#include <ctime>
#include <vector>
#include <cstdlib>

#define	MIN(A, B)	((A < B) ? A : B)

VND::VND(VRPTW& inVRPTW)
    :   INCR(inVRPTW, "VND"),
        vnRecord(inVRPTW),
        vnCurrent(inVRPTW),
        vnNeighbor(inVRPTW)
{
    memset(&vnRecordE, 0, sizeof(Sol::Eval));
    memset(&vnCurrentE, 0, sizeof(Sol::Eval));
    memset(&vnNeighborE, 0, sizeof(Sol::Eval));
    
    try
    {
		vnNeighborhoods = new Moves::Move*[Moves::getInstance().getNbNeighborhoods()];
	}
	catch(std::bad_alloc&)
	{	assert(false);	}
	
	this->reset_neighborhoods();
}


VND::~VND()
{
	delete [] vnNeighborhoods;
}


void    VND::execute(void* inArg)
{
    Sol*        inSol = (Sol*)inArg;
    unsigned	current = 0;
	unsigned	i = 0;		// iterateur sur voisinage
    unsigned	n = 0;		// nombre voisinage
    unsigned	k = 0;		// nombre voisinage dernierement parcourus
    unsigned	si = 0;		// iterateur sur sous-voisinage
    unsigned	fail = 0;
    unsigned	max_fail = rand() % 200;
    clock_t		init;
    clock_t		curren;
    
    assert(inSol != 0);
    
    init = clock();
    
    // cpy
    vnCurrent = *inSol;
    vnCurrent.eval(vnCurrentE);
    
    // recuperer tous les voisinages de vnCurrent
    this->reset_neighborhoods();
    n = Moves::getInstance().fillNeighborhoodsBuffer(vnCurrent, this->vnNeighborhoods);
    
    if (n == 0)
		return;
    
    //std::cout << n << std::endl;
    
    si = 0;
    
	for (;;)
	{
		vnNeighbor = vnCurrent;
		vnNeighborhoods[i]->execute(vnNeighbor, si);		
		vnNeighbor.eval(vnNeighborE);

		if (vnNeighborE < vnCurrentE)
		{
			vnCurrent = vnNeighbor;
			vnCurrentE = vnNeighborE;
			curren = clock();
			//std::cout << vnCurrentE.toString() << " in " << (((curren - init) / (1.0 * CLOCKS_PER_SEC))) << std::endl;
			this->reset_neighborhoods();
			n = Moves::getInstance().fillNeighborhoodsBuffer(vnCurrent, this->vnNeighborhoods);
			//std::cout << "neighborhoods count : " << n << std::endl;
			i %= n;
			k = 0;
			fail = 0;
		}
		else
		{
			//fail++;
			//if (fail > max_fail)
			//	break;
			++i %= n;
			if (k == n)
				//si++;
				break;
		}
		
		k++;
	}
	
	//std::cout << vnCurrentE.toString() << std::endl;
    *inSol = vnCurrent;
}


void	VND::reset_neighborhoods()
{
	memset(vnNeighborhoods, 0, Moves::getInstance().getNbNeighborhoods() * sizeof(void*));
}

// basic instinct
void	BasicInsert::execute(void* inArg)
{
	Sol::Eval		soleval;
	unsigned		free = 0;
	std::multimap<Sol::Eval, Trio>	insert_by_costs;
	unsigned char	to_insert = 0xff;
	
	assert(inArg != 0);
	
	std::vector<unsigned char>&	sequence = *(std::vector<unsigned char>*)inArg;
	
	assert(sequence.size() == slVRPTW.size());
	
	
	for (unsigned i = 0 ; i < sequence.size() ; i++)
	{
		to_insert = sequence[i];
		insert_by_costs.clear();
		
		slSol.eval(soleval);
		//std::cout << soleval.toString() << std::endl;
		
		if (soleval.seVehicles == 0)
		{
			slSol.getrVehicle(0).insert(to_insert, slVRPTW.size(), slVRPTW.size() + 1);
			continue;
		}
		else
		{
			for (unsigned j = 0 ; j < slVRPTW.size() ; j++)
			{
				Vehicle&	v = slSol.getrVehicle(j);
				Vehicle::Iterator	it1;
				Vehicle::Iterator	it2;
				
				if (v.veSuccs[v.bdepot().info().siClient] == v.edepot().info().siClient)
				{
					free = j;
					continue;
				}
				else if (v.contains(to_insert))
					continue;
				
				it1 = v.bdepot();
				it2 = it1;
				++it2;
				
				while (it2 != v.end())
				{
					if (	
#ifdef USING_CHECK_INSERT3
							slVRPTW.checkInsert3(	it1.info(),
													it2.info(),
													to_insert,
													v.edepot().info().siCCapacityAtArrival)
#endif
#ifdef USING_CHECK_INSERT4
							slVRPTW.checkInsert4(	v,
													it1.info().siClient,
													it2.info().siClient,
													to_insert,
													v.edepot().info().siCCapacityAtArrival)
#endif				
							!= VRPTW::REALIZABLE_NONE)
					{
						v.insert(to_insert, it1.info().siClient, it2.info().siClient);
						slSol.eval(soleval);
						//std::cout << "incr cost" << soleval.toString() << std::endl;
						insert_by_costs.insert(std::pair<Sol::Eval, Trio>(soleval, Trio(j, it1.info().siClient, it2.info().siClient)));
						v.erase(to_insert);
					}
					++it1;
					++it2;
				}
			}
		}
		
		if (insert_by_costs.size() == 0)
			slSol.getrVehicle(free).insert(to_insert, slVRPTW.size(), slVRPTW.size() + 1);
		else
		{
			// select best insert with virtual function to permit grasp
			unsigned	incr = rand() % MIN(this->getNRandInsert(), insert_by_costs.size());
			std::multimap<Sol::Eval, Trio>::iterator	itm;
			
			itm = insert_by_costs.begin();
			
			for (unsigned k = 0 ; k < incr ; k++, ++itm)
				;;
			
			slSol.getrVehicle(itm->second.first).insert(to_insert, itm->second.second, itm->second.third);
		}
	}
	
	//std::cout << slSol.toString() << std::endl;
}

unsigned	BasicInsert::getNRandInsert() const
{
	return (2);
}


